/**
 * file:   KMP.java
 * date:   2014-06-23
 * author: weiwei
 * desc:   KMP test
 */

import java.util.Arrays;

public class KMPtest {
	public static int[] getNextArray(String s) {
		char[] target = s.toCharArray();
		int size = target.length;
		int[] next = new int[size + 1];
		next[0] = 0;
		next[1] = 0;
		int k = 0; //第i次迭代开始之前，k表示next[i-1]的值
		for (int i = 2; i < size + 1; i++) {
			for (; k != 0 && target[k] != target[i - 1]; k = next[k]) {
			}
			if (target[k] == target[i - 1]) {
				k++;
			}
			next[i] = k;
		}
		return next;
	}

	public static void kmpmatch(String text, String pattern) {
		int m, n, s, q;
		int[] next = getNextArray(pattern);
		char[] textarray = text.toCharArray();
		char[] patternarray = pattern.toCharArray();
		m = patternarray.length;
		n = textarray.length;
		q = s = 0; // q表示上一次迭代匹配了多少个字符， s表示这次迭代从text的哪个字符开始比较
		while (s < n) {
			for (q = next[q]; q < m && patternarray[q] == textarray[s]; q++, s++) {
			}
			if (q == 0) {
				s++;
			} else if (q == m) {
				System.out.println("matched success at " + (s - m));
			}
		}
	}

	public static void main(String[] args) {
//		int[] next = getNextArray("abababca");
//		System.out.println(Arrays.toString(next));
		kmpmatch("bdcaccacaercacdcaca", "caca");
	}

}
